// 给定一个二叉树的根节点root,要求判断是否是一个有效的二叉搜索树

// 思路1：中序遍历，递增的有序序列，记录上一个遍历的值，如果不满足递增，则返回false
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function isValidBST(root) {
    let maxVal = -Infinity
    function dfs(root) {
        if (!root) {
            return true
        }
        let leftFlag = dfs(root.left)
        if (root.val > maxVal) {
            maxVal = root.val
        } else {
            return false
        }
        let rightFlag = dfs(root.right)
        return leftFlag && rightFlag
    }
    return dfs(root)
}

// 思路2：中序遍历，迭代
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，stack的大小

function isValidBST2(root) {
    if (!root) {
        return true
    }
    let stack = []
    let cur = root
    let pre = null
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            let node = stack.pop()
            if (pre && pre.val >= node.val) {
                return false
            }
            pre = node
            cur = node.right
        }
    }
    return true
}

// 思路3：前序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function isValidBST3(root) {
    function dfs(root, minVal, maxVal) {
        if (!root) {
            return true
        }
        if (root.val <= minVal) {
            return false
        }
        if (root.val >= maxVal) {
            return false
        }
        return dfs(root.left, minVal, root.val) && dfs(root.right, root.val, maxVal)
    }
    return dfs(root, -Infinity, Infinity)
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 8,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(isValidBST(root))
console.log(isValidBST2(root))
console.log(isValidBST3(root))